package PriorityQueue;

import java.util.Comparator;
import TDAMapeo.Entry;
import TDAMapeo.InvalidKeyException;

public class Heap<K,V> implements PriorityQueue<K,V> {

	protected Entry<K,V>[] e; 
	protected int size;
	protected Comparator<K> comp;
	
	
	public class Entrada<K,V> implements Entry<K,V>{
		protected K key;
		protected V value;
		public Entrada(K k, V v){
			key = k; value= v;
		}
		public K getKey(){
			return key;
		}
		public V getValue(){
			return value;
		}
	}
	
	public Heap(Comparator<K> comp){
		this.comp=comp;
		e = (Entry<K,V>[]) new Entrada[1000]; 
		size = 0;
	}
	
	public Heap(){
		this.comp= new DefaultComparator<K>();
		e = (Entry<K,V>[]) new Entrada[1000]; 
		size = 0;
	}
	
	public int size() {
		return size;
	}

	public boolean isEmpty() {
		return size==0;
	}

	public Entry<K, V> min() throws EmptyPriorityQueueException {
		if(isEmpty()) throw new EmptyPriorityQueueException("min(): cola vacia");
		return e[1];
		
	}

	public Entry<K, V> insert(K k, V v) throws InvalidKeyException {
		if(k == null) throw new InvalidKeyException("insert(): Key nula");
		
		if(size==e.length-1) reSize();
		
		Entry<K,V> nueva = new Entrada<K,V>(k,v);
		e[++size] = nueva ;
		int i = size;
		boolean sigue = true;
		while(sigue && i>1 ){
			if( comp.compare(e[i].getKey(),e[i/2].getKey()) <0 ){
				Entry<K,V> aux = e[i];
				e[i]=e[i/2];
				e[i/2] = aux;
				i = i/2;
			}
			else sigue = false;
		}
		
		return nueva;	
		
	}

	private void reSize(){
		Entry<K,V> aux [] = (Entry<K,V>[])  new Entrada[size*2];
		for( int i = 1;i<=size() ;i++){
			aux[i] = e[i];
		}
		e = aux;
	}
	
	public Entry<K, V> removeMin() throws EmptyPriorityQueueException {
		if(isEmpty()) throw new EmptyPriorityQueueException("removeMin(): Cola vacia ");
		Entry<K,V> salida = e[1];
		if(size==1) { e[size] = null;size=0; }
		else{
			e[1] = e[size]; e[size] = null; size--; 
			boolean seguir = true;
			int i = 1;
			while( seguir){
				boolean tieneIzq = i*2 <=size ;
				boolean tieneDer= i*2+1 <=size ;
				int m ;
				if(!tieneIzq){
					seguir = false;
				}
				else{
					if(tieneDer){
						int c = comp.compare(e[i*2].getKey(),e[i*2+1].getKey());
						if(c>0){
							m= i*2+1;
						} else m = i*2;
					}else{
						m= i*2;
					}
				if(comp.compare(e[i].getKey(),e[m].getKey())>0){
					Entry<K,V> aux = e[m];
					e[m] = e[i] ;
					e[i] = aux;
					i=m;
				}
				else seguir = false;
				}
			}
			
		}
		return salida;
	}
	
	
}





